package com.cat.dataStructure02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-integers-with-popcount-depth-equal-to-k-ii/
 * @create 2025/11/1 09:40
 * @since JDK17
 */

class Solution90 {
    class Fenwick {
        int[] tree;
        Fenwick(int n) {
            tree = new int[n + 1];
        }
        void update(int i, int val) {
            while (i < tree.length) {
                tree[i] += val;
                i += i & -i;
            }
        }
        int pre(int i) {
            int ans = 0;
            while (i > 0) {
                ans += tree[i];
                i -= i & -i;
            }
            return ans;
        }
        int query(int l, int r) {
            return pre(r) - pre(l - 1);
        }
    }
    public int[] popcountDepth(long[] nums, long[][] queries) {
        int n = nums.length, m = 0;
        Fenwick[] f = new Fenwick[6];
        Arrays.setAll(f, x -> new Fenwick(n));
        for (int i = 0; i < n; i++) {
            update(i, nums[i], 1, f);
        }
        for (var q : queries) {
            m += q[0] == 1 ? 1 : 0;
        }
        int[] ans = new int[m];
        int idx = 0;
        for (var q : queries) {
            if (q[0] == 1) {
                ans[idx++] = f[(int) q[3]].query((int) q[1] + 1, (int )q[2] + 1);
            } else {
                int i = (int) q[1];
                update(i, nums[i], -1, f);
                nums[i] = q[2];
                update(i, nums[i], 1, f);
            }
        }

        return ans;
    }
    void update(int i, long x, int delta, Fenwick[] f) {
        int d = popDepth(x);
        f[d].update(i + 1, delta);
    }
    int popDepth(long x) {
        int ans = 0;
        while (x > 1) {
            ans++;
            x = Long.bitCount(x);
        }
        return ans;
    }
}